package com.hp.interview.design;

import java.util.HashMap;
import java.util.Map;

/**
 * 自己实现LRU
 * 原理：
 * 1、底层原理就是一个固定容量的HashMap
 * 2、另外维护一个链表结构和一个head、tail指针
 * 3、get、put元素时，都是操作这个map；只是要附加一个将这个元素放到链表表头的操作
 * 4、put元素时如果超过容量，就拿到链表的表尾元素，然后用map移除这个元素
 *
 * @author hupan
 * @date 2021-05-14 18:53
 */
public class LRUCache<K, V> {
    class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev, next;

        public Node() {
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final HashMap<K, Node<K, V>> map;
    private final Node<K, V> head;
    private final Node<K, V> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        head = new Node<>();
        tail = new Node<>();
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            return null;
        }
        moveNodeToHead(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            if (map.size() >= capacity) {
                map.remove(tail.prev.key);
                removeTailNode();
            }
            Node<K, V> newNode = new Node<>(key, value);
            map.put(key, newNode);
            addToHead(newNode);
        } else {
            node.value = value;
            moveNodeToHead(node);
        }
    }

    private void addToHead(Node<K, V> newNode) {
        newNode.prev = head;
        newNode.next = head.next;
        head.next.prev = newNode;
        head.next = newNode;
    }

    private void moveNodeToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void removeTailNode() {
        removeNode(tail.prev);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("{");
        for (Map.Entry<K, Node<K, V>> entry : map.entrySet()) {
            Node<K, V> node = entry.getValue();
            sb.append(node.key.toString()).append(":").append(node.value.toString()).append(", ");
        }

        sb.replace(sb.lastIndexOf(","), sb.lastIndexOf(",") + 2, "");
        sb.append("}");

        return sb.toString();
    }

    public static void main(String[] args) {
        LRUCache<Integer, Integer> lruCache = new LRUCache<>(3);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.get(1);
        lruCache.put(4, 4);

        // toString 我就没贴了，代码太长了
        System.out.println(lruCache);
    }

}